/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
//链表拼接+拆分
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr)
            return nullptr;
        Node* cur=head;
        //复制node和next构建拼接链表
        while(cur!=nullptr)
        {
            Node* node=new Node(cur->val);
            
            node->next=cur->next;
            cur->next=node;

            cur=node->next;
        }
        cur=head;
        //复制random
        while(cur!=nullptr)
        {
            if(cur->random!=nullptr)
            {
                cur->next->random=cur->random->next;
            }
            //不满足，当random此时为null时，上步复制构造函数中默认初始化为null
            cur=cur->next->next;
        }
        
        //拆分链表
        cur=head->next;
        Node* pre=head,*res=head->next;
        while(cur->next!=nullptr)
        {
            pre->next=pre->next->next;
            cur->next=cur->next->next;
            pre=pre->next;
            cur=cur->next;
        }
        pre->next=nullptr;
        return res;
    }
};

//哈希
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* cur=head;
        unordered_map<Node*,Node*>map;
        //建立Map
        while(cur!=nullptr)
        {
            map[cur]=new Node(cur->val);
            cur=cur->next;
        }
        cur=head;
        //建立Map中链表的链接
        while(cur!=nullptr)
        {
            map[cur]->next=map[cur->next];
            map[cur]->random=map[cur->random];
            cur=cur->next;
        }
        return map[head];
    }
};